package Syntax;

import Lexical.Token;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Syn {

    private ArrayList<Production> Prod_list = new ArrayList<Production>();// 记录2型 文法产生式
    //private ArrayList<String> terminal_inputs = new ArrayList<String>();//记录该文法 可能输入哪些终结符
    private Map<Integer , Set<Item>> item_Set_collection = new HashMap<>();
    private int itemSetNum = 0;//项目集族 中 项目集的数量
    ArrayList<AnalysisTable>  analysisTables = new ArrayList<AnalysisTable>();


    public Syn(String synFile){

        FileReader fr; //将 文法规则读入 读入
        BufferedReader bfr;
        try {
            fr = new FileReader(synFile);
            bfr = new BufferedReader(fr);

            String line;
            String temp;
            while( ( line = bfr.readLine() )!=null)
            {
                if (line.contains("%%%"))
                {
                    continue;
                }

                Production one_Prod = new Production();
                //System.out.println( line );//###
                if( line.substring( 0, 3 ).equals("NT:") )
                {
                    one_Prod.setLeft( line.substring(3) );
                }
                while( !( temp = bfr.readLine() ).contains("%%%")  )
                {
                    //System.out.println( temp );//###
                    Symbol symbol_right = new Symbol();
                    if( temp.substring( 0, 3 ).equals("NT:") )
                    {
                        symbol_right.setType("NonTerminal");
                        symbol_right.setContent( temp.substring(3) );
                    }
                    else
                    {
                        symbol_right.setType("Terminal");
                        symbol_right.setContent( temp.substring(3) );
                    }
                    //System.out.println( symbol_right.getContent() );//####
                    one_Prod.addRightSymbol( symbol_right );
                }

                Prod_list.add( one_Prod );
            }

        }
        catch (FileNotFoundException e)
        {
            System.out.println("读取文件失败: "+synFile);
            System.exit(0);
        }
        catch (IOException e)
        {
            System.out.println("读取文件失败: "+synFile);
            System.exit(0);
        }
    }


    public void showProds(){
        for(Production prod: Prod_list )
        {
            showProd(prod);
        }
    }
    public void showProd(Production prod){//展示一个产生式
        System.out.print( "产生式："+prod.getLeft() + " -> " );
        for(Symbol sym: prod.getRight() )
        {
            System.out.print(" " + sym.getContent() );
        }
        System.out.println("\n");
    }
    public void showItem(Item item)//展示一个项目
    {
        System.out.print("项目:" + item.getLeft()+"->");
        for(int i=0; i<item.getRight().size(); i++)
        {
            if( i == item.getPoint_index() )
                System.out.print("·");
            System.out.print(" "+item.getRight().get(i).getContent());
        }
        if( item.getPoint_index() == item.getRight().size() )
        {
            System.out.print("·");
        }
        System.out.print(" , ");
        for(String s: item.getForwards())
        {
            System.out.print(" "+s);
        }
        System.out.println("\n");
    }

    public void collection_ItemSet(){
        //Set<Set<Item>> item_Set_collection = new HashSet<Set<Item>>();


        Symbol init_sym = new Symbol();
        init_sym.setContent(this.Prod_list.get(0).getLeft());//获取开始符号
        init_sym.setType("NonTerminal");
        Item init = new Item();
        init.setLeft("Accept");//从文法的基本项目 Accep -> ·S，#开始构造 项目集族
        init.addRightSymbol(init_sym);
        init.addForward( "#" );
        init.setPoint_index(0);

        Production extend_Prod = new Production();//产生式增加  增广文法 Accept->S
        extend_Prod.setLeft("Accept");
        extend_Prod.addRightSymbol(init_sym);
        this.Prod_list.add(extend_Prod);

        Set<Item> I0_Items = new HashSet<Item>();
        Set<Item> new_items = new HashSet<Item>();
        new_items.add(init);
        closure(I0_Items, new_items);//计算得 最开始的 项目集I0
        item_Set_collection.put(itemSetNum, I0_Items);//I0存入项目集族中 <0,I0>
        itemSetNum++;
        /*System.out.println("I0项目集内容");
        for(Item i: I0_Items)
        {
            this.showItem(i);
        }*/
        /*Set<Item> I1 =  GO(I0_Items, init_sym);
        System.out.println("I1项目集内容");
        for(Item i: I1)
        {
            this.showItem(i);
        }*/

        this.createCollection(0);
        for( int i=0; i<this.itemSetNum; i++)//展示所有项目集
        {
            Set<Item> Ix = this.item_Set_collection.get(i);
            System.out.println("项目集I"+i+"的内容为：");
            for( Item item_Ix: Ix)
            {
                this.showItem(item_Ix);
            }
        }
    }

    public void createCollection( int itemSetIndex )//构造项目集族
    {
        if(itemSetIndex >= this.itemSetNum )
            return;
        Set<Item> Ix_itemSet = this.item_Set_collection.get( itemSetIndex );
        /*System.out.println("项目集I"+itemSetIndex+"的内容为：");//####
        for( Item item_Ix: Ix_itemSet)//###
        {
            this.showItem(item_Ix);
        }*/
        Set<Symbol> inputs = this.acquire_itemSet_input(Ix_itemSet);

        for(Symbol sym: inputs)
        {
            Set<Item> new_ItemSet = GO(Ix_itemSet, sym);
            boolean isNew = true;
            for(int i=0; i<itemSetNum; i++)//查看 项目集族中此项目集是否已经产生过了
            {
                if( this.itemSetEquals(item_Set_collection.get(i), new_ItemSet ) )
                {
                    //GO函数记录 LR(1)分析表中 移入动作的信息
                    this.putIn_OR_GOTO(itemSetIndex, sym, i);
                    //记录归约信息

                    isNew = false;
                    break;
                }
            }
            if( isNew )
            {
                /*System.out.println("GO( I"+itemSetIndex+" , "+sym.getContent()+"):");//####
                for(Item temp: new_ItemSet)//###
                {
                    this.showItem(temp);
                }*/
                //GO函数记录 LR(1)分析表中 移入动作的信息
                this.putIn_OR_GOTO(itemSetIndex, sym, itemSetNum);
                //记录归约信息
                this.reduce_OR_Accept(new_ItemSet, itemSetNum);
                item_Set_collection.put(itemSetNum, new_ItemSet);
                itemSetNum++;
            }
        }
        this.createCollection( itemSetIndex+1 );//继续 让没有GO过的 项目集 GO
    }
    public void reduce_OR_Accept(Set<Item> analysis_items, int itemNum )
    {
        Symbol init_sym = new Symbol();
        init_sym.setContent(this.Prod_list.get(0).getLeft());//获取开始符号
        init_sym.setType("NonTerminal");
        Item acc = new Item();
        acc.setLeft("Accept");
        acc.addRightSymbol(init_sym);
        acc.addForward( "#" );
        acc.setPoint_index(1);
        //acc项目是 Accept->S·，# 含有这个项目的项目集 在输入#情况下完成分析完成Accept
        //如果项目集中含有 像A->b·，c 的项目 那么 该项目集代表的状态 在输入c时 依据A->b进行归约
        for(Item i: analysis_items)
        {
            if( i.equals(acc) ) //先判断acc情况 因为 acc情况是一种特殊的归约
            {
                AnalysisTable accept = new AnalysisTable();
                accept.setCurrent_statue(itemNum);
                accept.setAct("Accept");
                Symbol end = new Symbol();
                end.setContent("#");
                end.setType("Terminal");
                accept.setInput(end);
                this.analysisTables.add(accept);
                return;
            }
            if( i.getPoint_index() == i.getRight().size() )//归约
            {
                for(String s: i.getForwards())//对于每个向前搜索符都要有 一条信息
                {
                    Symbol forward = new Symbol();
                    forward.setType("Terminal");
                    forward.setContent(s);

                    AnalysisTable reduce = new AnalysisTable();
                    reduce.setCurrent_statue(itemNum);
                    reduce.setInput(forward);
                    reduce.setAct("reduce");
                    reduce.getReduce_Prod().setLeft( i.getLeft() );
                    reduce.getReduce_Prod().getRight().addAll( i.getRight() );

                    this.analysisTables.add(reduce);
                }
                continue;//可能有多条项目 可以产生归约信息
            }
        }
    }
    public void putIn_OR_GOTO(int current_status, Symbol input_sym, int target_status)
    {
        if( input_sym.getType().equals("NonTerminal"))//是非终结符 那么是GOTO表的信息
        {
            AnalysisTable GOTO = new AnalysisTable();
            GOTO.setCurrent_statue(current_status);
            GOTO.setAct("GOTO");
            GOTO.setInput(input_sym);
            GOTO.setTarget_status(target_status);
            this.analysisTables.add(GOTO);
        }
        else //是终结符 就是移入 信息
        {
            AnalysisTable put_in = new AnalysisTable();
            put_in.setCurrent_statue(current_status);
            put_in.setAct("put_in");
            put_in.setInput(input_sym);
            put_in.setTarget_status(target_status);
            this.analysisTables.add(put_in);
        }
    }

    public Set<Symbol> acquire_itemSet_input(Set<Item> itemSet)
    {//获取一个项目集 可能面对的输入 例如 S->·R ， #   R->·*L , =  那么这个项目集 所面对的输入可能是 R和*
        Set<Symbol> inputs = new HashSet<Symbol>();
        if( itemSet == null )
            return inputs;
        for( Item i: itemSet)
        {
            if( i.getPoint_index() == i.getRight().size() )//例如 项目集 中一个项目 R->L·, # 对应没有输入了
                continue;
            else
            {
                inputs.add( i.getRight().get(i.getPoint_index()) );
            }
        }
        return inputs;
    }
    public Set<Item> GO(Set<Item> I, Symbol X)
    {
        Set<Item> complete_ItemSet = new HashSet<Item>();
        Set<Item> init_ItemSet = new HashSet<Item>();
        for(Item one: I)
        {
            if( one.getPoint_index() == one.getRight().size() )//像 S->aBc· , # 这种已经都输入完的 就不用管了
                continue;
            if( one.getRight().get(one.getPoint_index()).equals(X) )//例如 X是L  此时项目集I中有项目 S->·L=R , # 那么就要将 S->·L=R变为S->L·=R , # 作为新项目集的一部分
            {                                                       //并以此为基础 依靠闭包函数 生成完整的 项目集
                Item new_item = new Item(one);
                new_item.setPoint_index( new_item.getPoint_index()+1 );
                init_ItemSet.add( new_item );
            }
        }
        return closure( complete_ItemSet, init_ItemSet);
    }

    public Set<Item> closure(Set<Item> AllItems, Set<Item> last_new_items)
    {
        Set<Item> new_items = new HashSet<Item>();
        if( last_new_items.size()==0 )
            return new_items;
        AllItems.addAll( last_new_items );

        for(Item aItem: last_new_items )
        {
            if( aItem.getPoint_index() == aItem.getRight().size())//像 S->aBc· , # 这种已经都输入完的 就不用管了
            {
                continue;
            }
            else
            {
                Symbol index_sym = aItem.getRight().get(aItem.getPoint_index());
                if( aItem.getPoint_index()!=aItem.getRight().size() && index_sym.getType().equals("NonTerminal") )// 找项目集中类似 A->a·Xb 的式子 将X->·y加入项目集
                {
                    for( Production p: this.Prod_list)
                    {
                        if( p.getLeft().equals( index_sym.getContent() ) )
                        {
                            Item temp_item = new Item();
                            temp_item.setLeft( p.getLeft() );
                            temp_item.setRight( p.getRight() );
                            temp_item.setPoint_index(0);
                            temp_item.setForwards( forwards_first(aItem) );
                            //如果是项目心一样的式子就要 把 向前搜索符凑一起
                            boolean isNew = true;
                            for( Item i: AllItems)
                            {
                                if( this.itemCoreEquals(i, temp_item))
                                {
                                    i.getForwards().addAll( temp_item.getForwards() );
                                    isNew = false;
                                }
                            }
                            if( isNew )//this.hasItem(AllItems, temp_item)
                            {
                                new_items.add(temp_item);
                            }
                        }
                    }
                }
            }
        }
        /*System.out.println("目前 项目集内容为：");//####
        for(Item i: AllItems)
        {
            this.showItem(i);
        }
        System.out.println("拓展得到的项目：");//###
        for(Item i: new_items)
        {
            this.showItem(i);
        }*/
        closure(AllItems, new_items);

        return  AllItems;
    }
    public boolean itemCoreEquals(Item a, Item b)
    {
        if( a.getLeft().equals(b.getLeft()) && a.getPoint_index()== b.getPoint_index() && Production.listEquals(a.getRight(), b.getRight()))
            return true;
        return false;
    }
    public boolean hasItem(Set<Item> items, Item i)//已经重写了 各个类的hashCode函数
    {
        /**HashSet的contains 不同于 ArrayList的contains  不是重写equals函数就可以的
         * 关键在于 Java中hashCode与equals方法的紧密联系. hashCode() 是Object类定义的另一个基础方法.
         * 没有重写hashCode函数 是不能正常使用 set的contains函数的
         * set中比较两者 相同 是先比较 两者对象的哈希值是否相同
         * 默认情况下是 每个对象有自己的哈希值 那么 就算两个对象内容相同 但是使用默认的hashCode函数 产生不同的哈希值 直接否定了两者相等**/
        for(Item temp: items)
        {
            if( temp.equals(i) )
                return true;
        }
        return false;
    }
    public boolean itemSetEquals(Set<Item> set1, Set<Item> set2 )
    {
        if( set1.size() != set2.size() )
            return false;
        else
        {
            for( Item i: set1)
            {
                if( !set2.contains(i) )
                    return false;
            }
        }
        return true;
    }
    public Set<String> forwards_first(Item item)//下面那个 函数实现时 脱离了LR(1) 的要求 变成了求follow集
    {                                   //重写 求向前搜索符的函数
        //例如 S->·A  闭包拓展后 得到A->·*，#  其中求得A->·*是前面闭包函数的事  而#的求得是根据原来的项目S->·A
        Set<String> forwards = new HashSet<String>();
        if( item.getPoint_index() >= item.getRight().size()-1 ) //S->·A   A后面没有东西 那么A->·*的向前搜索符为 # 加上 S->·A本身的向前搜索符
        {                                                       //
            forwards.add("#");
            forwards.addAll( item.getForwards() );
            return forwards;
        }
        else
        {
            Symbol afterNTermal = item.getRight().get(item.getPoint_index()+1);
            if( afterNTermal.getType().equals("Terminal") )
            {
                forwards.add(afterNTermal.getContent());
                return forwards;
            }
            else
            {
                forwards.addAll( this.first(afterNTermal) );
                return forwards;
            }
        }

    }
    public Set<String> forwards_follow( String NT_content )//计算 A->a·Bp 计算follow(B)作为B的向前搜索符 只有非终结符 需要规约而需要计算这个信息
    {
        Set<String> forwards = new HashSet<String>();
        Symbol nt = new Symbol();
        nt.setType("NonTerminal");
        nt.setContent(NT_content);
        for(Production p: this.Prod_list)
        {
            if( p.getRight().contains(nt) )//先要找到 像 A->aBp 或者 A->acB 的包含B的产生式  才能根据 这些产生式 求B的向前搜索符
            {//默认的contains函数会调用equals函数 而默认的equals函数是比较两个对象的地址是否一样 故需要重写equals方法
                //System.out.print("找到式子:");//####
                //showProd(p);//###
                int NT_index = p.getRight().indexOf( nt );
                if( NT_index == p.getRight().size()-1 )//是最后一个符号 那么first 为#
                {
                    forwards.add("#");
                    continue;
                }
                else
                {
                    forwards.addAll( first( p.getRight().get(NT_index+1) ) );
                    continue;
                }
            }
        }
        return forwards;
    }

    public Set<String> first(Symbol sym)
    {
        Set<String> firstSet = new HashSet<String>();
        if( sym.getType().equals("Terminal"))//如果 是终结符 那么它的first集就是自己
        {
            firstSet.add( sym.getContent() );
            return firstSet;
        }
        if( sym.getType().equals("NonTerminal") )// 在产生式中用 @代表 空
        {
            for(Production p: this.Prod_list)
            {
                if( p.getLeft().equals( sym.getContent() ) )//求A的first集 得找到A->aB 类似的式子
                {
                    //System.out.print("找到了式子:");//####
                    //showProd(p);//###
                    Symbol first_sym = p.getRight().get(0); // 获得产生式右边第一个符号第一个符号  在产生式中用 @代表 空
                    /*if ( first_sym.getContent().equals("@") )//偷懒 这边对于 文法进行了限制 任意一个非终结符的first集不可能为空
                    {
                        firstSet.add("@");
                        continue;
                    }
                    else */
                    if( first_sym.getType().equals("Terminal") )
                    {
                        firstSet.add( first_sym.getContent() );
                        continue;
                    }
                    else
                    {
                        firstSet.addAll( first( first_sym ) );
                        continue;
                    }
                }
            }
        }
        return firstSet;
    }

    public void showAnalysisTables()
    {
        for( AnalysisTable a: this.analysisTables)
        {
            if( a.getAct().equals("put_in"))
            {
                System.out.println("状态 "+a.getCurrent_statue()+"在输入为："+a.getInput().getContent()+" 的情况下，移入状态"+a.getTarget_status());
            }
        }
        for( AnalysisTable a: this.analysisTables)
        {
            if( a.getAct().equals("reduce"))
            {
                System.out.println("状态 "+a.getCurrent_statue()+"在输入为："+a.getInput().getContent()+" 的情况下，依据如下产生式进行归约");
                this.showProd( a.getReduce_Prod() );
            }
        }
        for( AnalysisTable a: this.analysisTables)
        {
            if( a.getAct().equals("Accept"))
            {
                System.out.println("状态 "+a.getCurrent_statue()+"在输入为："+a.getInput().getContent()+" 的情况下，语法分析完成Accept");
            }
        }
        for( AnalysisTable a: this.analysisTables)
        {
            if( a.getAct().equals("GOTO"))
            {
                System.out.println("状态 "+a.getCurrent_statue()+"在输入为："+a.getInput().getContent()+" 的情况下，GOTO转入状态"+a.getTarget_status());
            }
        }
    }

    public void parsing(ArrayList<Token> tokenList)
    {
        Stack<Integer> status_stack = new Stack<Integer>();//状态栈

        status_stack.push(0);
        Stack<Symbol> symbol_stack = new Stack<Symbol>();//符号栈

        for(int token_index=0; token_index<tokenList.size(); token_index++)
        {
            /*System.out.println("\n当前状态栈");//####
            for(Integer interger : status_stack)//####
            {
                System.out.print(" "+interger);
            }*/
            System.out.println("\n当前符号栈");//####
            for(Symbol sym : symbol_stack)//####
            {
                System.out.print(" "+sym.getContent());
            }
            System.out.print("\n");//####
            //////////////////////////////
            Token token = tokenList.get(token_index);
            System.out.println("准备输入符号："+ token.getOrigin());

            int status_top =  status_stack.peek();
            Symbol current_input = new Symbol();
            current_input.setType("Terminal");
            current_input.setContent( token.getClassification() );//这是 一类词作为输入 例如 标识符 identifier

            AnalysisTable action = how_to_do(status_top, current_input);//根据LR(1)分析 查找 在 当前栈顶符号 下 输入 当前符号 需要进行什么动作
            if( action == null )
            {
                current_input.setContent( token.getOrigin() );//这是 具体的内容作为输入 例如 void
                action = how_to_do(status_top, current_input);
                if( action == null )
                {
                    System.out.println("出错！ 在第"+token.getLine_Num()+"行");
                    System.exit(0);
                }
            }
            //System.out.println("当前需要进行的行为是："+action.getAct());//##########
            if( action.getAct().equals("put_in") )
            {
                status_stack.push( action.getTarget_status() );
                symbol_stack.push( current_input );
            }
            else if( action.getAct().equals("reduce") )
            {
                Production reduce_Prod = action.getReduce_Prod();
                int size = reduce_Prod.getRight().size();
                for(int i=0; i<size; i++)
                {//两个栈 内关于 产生式右部内容都弹出 进行归约
                    status_stack.pop();
                    symbol_stack.pop();
                }

                int GOTO_status_top = status_stack.peek();
                Symbol GOTO_NonTerminal = new Symbol();
                GOTO_NonTerminal.setContent( reduce_Prod.getLeft() );
                GOTO_NonTerminal.setType("NonTerminal");
                AnalysisTable GOTO_Action = how_to_do( GOTO_status_top, GOTO_NonTerminal );//一个归约 会配合一次GOTO
                status_stack.push( GOTO_Action.getTarget_status() );//状态栈移入 GOTO的结果
                symbol_stack.push( GOTO_NonTerminal );//符号栈移入归约后的符号
                token_index--;//前面输入的 符号并没有处理 下一个回合继续处理
            }
            else if( action.getAct().equals("Accept") )
            {
                System.out.println("Yes, syntax analysis is finished without error");
            }
        }
    }

    public AnalysisTable how_to_do( int current_status, Symbol input )
    {

        for( AnalysisTable a: this.analysisTables)
        {
            if( a.getCurrent_statue() == current_status && a.getInput().equals(input))
            {
                return a;
            }
        }
        return null;
    }
}
